COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00007 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a48.tex[154,phy] \today\hfill}

\bigskip
\line{\bf Factoring Input-Output Relations \hfil}

Let $M$ be a GSM with states $Q$, input alphabet $\Sigma$, and output
alphabet~$\Delta$, where $\Sigma\cap\Delta=\emptyset$. A~computation
of~$M$ is a string $q↓0x↓1y↓1q↓1x↓2y↓2q↓2\ldots x↓ny↓nq↓n$, where
$q↓0\in S$, $q↓n\in F$, and $q↓{i-1}x↓iy↓iq↓i$ is a transition of~$M$.
It is clear that the computations of~$M$ are a regular set,~$r$. Let
$h↓1$ be the homomorphism that maps characters of~$\Sigma$ into themselves,
and those of~$Q$ and~$\Delta$ into~$\epsilon$. Similarly, $h↓2$ maps
characters of~$\Delta$ into themselves, and others into~$\epsilon$.
If $xR↓My$ ($R↓M$ is the input-output relation of~$M$), there is a
computation~$z$ in~$r$, such that $zh↓1x$, $zh↓2y$. That is, $xh↓1↑{-1}zI↓rzh↓2y$,
so $x(h↓1↑{-1}\circ I↓r\circ h↓2)y$.

Conversely, suppose some strings $x$, $y$ are in the relation $x(h↓1↑{-1}
\circ I↓r\circ h↓2)y$. Then there must be strings $z$, $z'$ with
$xh↓1↑{-1}zI↓rz'h↓2y$. Then $z=z'$, so $z\in r$, $zh↓1x$, $zh↓2y$;
that is, $z$~is a computation of~$M$ with input~$x$ and output~$y$, so
$xR↓My$. Concluding, the input-output output relation of a GSM is
the composition of an inverse (i.e., converse)
homomorphism, a~filter for a regular
expression, and a homomorphism.

Conversely, those three types of relation are all input-output relations
of certain  GSMs, so their composition is. Therefore:

\proclaim Theorem. A relation is the IO relation of some GSM if and only if
it is the composition of an inverse homomorphism, a~filter for a regular
expression, and a homomorphism.

What do we do with this wierd-sounding theorem? It gives a simple way to
check whether a class of languages is closed under GSM mappings, as FMLs
and CFLs are:

\proclaim Corollary. A class of languages is closed under GSM mappings if
and only if it is closed under all homomorphisms, inverse homomorphisms,
and intersections with regular sets.

For example, to see if DPDLs are closed under GSM mappings. They are readily
shown closed under intersection with regular sets, because the DPDM can keep
track of prefix equivalence classes as it reads. They are also closed under
the inverse of a homomorphism, because the DPDM can apply the homomorphism
as it reads, using a finite buffer. They are not, however, closed under
homomorphism, because the DPDL $\{a↑ib↑ic↑j\}\cup\{d↑ie↑jf↑j\}$ is readily
mapped into the inherently ambiguous CFL $\{\,a↑ib↑jc↑k\mid i=j∨j=k\,\}$.
This also shows that the class of unambiguous CFLs is not closed under
GSM mappings.


\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd.
First draft (not published)
May 29, 1986.
%revised date;
%subsequently revised.

\bye